# !/usr/bin/env python
# -*- coding: utf-8 -*-
from decimal import Decimal


def heuristic(node, goal='TY'):
    # Heuristic function (for simplicity, we assume the heuristic values)
    heuristics = {'TSW': 23.28, 'YL': 19.39, 'LMC': 18.7, 'LW': 22.59, 'SS': 23.93, 'TM': 19.89, 'KT': 15.5,
                  'SK': 14.74, 'TLC': 14.43, 'TW': 7.33, 'KC': 3.43, 'TY': 0}
    return heuristics.get(node, float('inf'))


def a_star(graph, start, goal):
    # Priority queue for A* search (using f(n) = g(n) + h(n))
    open_list = [(0 + heuristic(start), 0, start, [start])]  # (f(n), g(n), node, path)
    visited = set()  # To keep track of visited nodes

    while open_list:
        # Sort by f(n) = g(n) + h(n)
        open_list.sort()
        f, g, current_node, path = open_list.pop(0)

        if current_node == goal:
            return path, round(g, 2)

        visited.add(current_node)

        # Explore neighbors
        for neighbor, distance in graph[current_node].items():
            if neighbor not in visited:
                new_cost = g + distance
                open_list.append((new_cost + heuristic(neighbor), new_cost, neighbor, path + [neighbor]))

    return None, None  # No path found


if __name__ == '__main__':
    graph = {
        'TSW': {'YL': 3.89},
        'YL': {'TSW': 3.89, 'TM': 7.57, 'LMC': 10.92, 'KT': 3.89},
        'LMC': {'YL': 10.92, 'LW': 3.89, 'SS': 3.42, 'SK': 3.96},
        'LW': {'LMC': 3.89, 'SS': 1.34},
        'SS': {'LW': 1.34},
        'TM': {'YL': 7.57, 'TLC': 5.46},
        'KT': {'YL': 3.89, 'SK': 3.43, 'TW': 8.17},
        'SK': {'KT': 3.43, 'LMC': 8.96, 'TW': 7.41},
        'TLC': {'TM': 5.46, 'TW': 7.1},
        'TW': {'KT': 8.17, 'TLC': 7.1, 'SK': 7.41, 'KC': 3.9},
        'KC': {'TW': 3.9, 'TY': 3.43},
        'TY': {'KC': 3.43}
    }

    # BFS
    bfs_path, bfs_cost = a_star(graph, 'TSW', 'TY')
    print(f"BFS Path: {bfs_path}, Total Distance: {bfs_cost} km")
    bfs_path, bfs_cost = a_star(graph, 'TSW', 'TY')
    print(f"BFS optima Path: {bfs_path}, Total Distance: {bfs_cost} km")
